SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Kempner function</title>

</head>

Kempner function

</h1>

</header>

In <a href="Number_theory" title="Number theory">number theory</a>, the Kempner function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S(n)}</annotation>

</semantics>

</math><img src="./896aa95cb194816f48a89fecd7e304d4b7f1af71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.703ex; height:2.843ex;" alt="{\displaystyle S(n)}" loading="lazy"><a href="#cite_note-oeis-1">[1]</a> is defined for a given <a href="Positive_integer" class="mw-redirect" title="Positive integer">positive integer</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> to be the smallest number <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> <a href="Divides" class="mw-redirect" title="Divides">divides</a> the <a href="Factorial" title="Factorial">factorial</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s!}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s!}</annotation>

</semantics>

</math><img src="./6aa320847120ad3c4a0ea45fbd40a086e7d0fd9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.737ex; height:2.176ex;" alt="{\displaystyle s!}" loading="lazy">. For example, the number <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 8}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 8}</annotation>

</semantics>

</math><img src="./1aaa997e6ad67716cfaa9a02c4df860bf60a95b5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 8}" loading="lazy"> does not divide <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1!}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1!}</annotation>

</semantics>

</math><img src="./5406cdb9ff60d5362462a57575cff2a566b46eac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.809ex; height:2.176ex;" alt="{\displaystyle 1!}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2!}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2!}</annotation>

</semantics>

</math><img src="./bf1a7180773383ece2005189939fad7c7505c32d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.809ex; height:2.176ex;" alt="{\displaystyle 2!}" loading="lazy">, or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 3!}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 3!}</annotation>

</semantics>

</math><img src="./48e39328d0c8decb40084ce547c5da090bb84992.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.809ex; height:2.176ex;" alt="{\displaystyle 3!}" loading="lazy">, but does divide <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 4!}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 4!}</annotation>

</semantics>

</math><img src="./cb4c418d1309a05092ea9dc6a1f9940e3b2d29bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.809ex; height:2.176ex;" alt="{\displaystyle 4!}" loading="lazy">, so <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S(8)=4}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S(8)=4}</annotation>

</semantics>

</math><img src="./a71f4cee815cfc997c1f75d52a4efaaf2b8db4dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.732ex; height:2.843ex;" alt="{\displaystyle S(8)=4}" loading="lazy">.

This function has the property that it has a highly inconsistent <a href="Asymptotic_analysis" title="Asymptotic analysis">growth rate</a>: it <a href="Linear_function" title="Linear function">grows linearly</a> on the <a href="Prime_number" title="Prime number">prime numbers</a> but only grows <a href="Logarithmic_growth" title="Logarithmic growth">sublogarithmically</a> at the factorial numbers.

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

This function was first considered by <a href="Fran%C3%A7ois_%C3%89douard_Anatole_Lucas" class="mw-redirect" title="François Édouard Anatole Lucas">François Édouard Anatole Lucas</a> in 1883,<a href="#cite_note-history1-2">[2]</a> followed by <a href="Joseph_Jean_Baptiste_Neuberg" title="Joseph Jean Baptiste Neuberg">Joseph Jean Baptiste Neuberg</a> in 1887.<a href="#cite_note-history2-3">[3]</a> In 1918, <a href="Aubrey_J._Kempner" title="Aubrey J. Kempner">A. J. Kempner</a> gave the first correct algorithm for computing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S(n)}</annotation>

</semantics>

</math><img src="./896aa95cb194816f48a89fecd7e304d4b7f1af71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.703ex; height:2.843ex;" alt="{\displaystyle S(n)}" loading="lazy">.<a href="#cite_note-history3-4">[4]</a>

The Kempner function is also sometimes called the Smarandache function following Florentin Smarandache's rediscovery of the function in 1980.<a href="#cite_note-5">[5]</a>

<div class="mw-heading mw-heading2"><h2 id="Properties">Properties</h2></div>

Since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> divides <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n!}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n!}</annotation>

</semantics>

</math><img src="./bae971720be3cc9b8d82f4cdac89cb89877514a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.042ex; height:2.176ex;" alt="{\displaystyle n!}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S(n)}</annotation>

</semantics>

</math><img src="./896aa95cb194816f48a89fecd7e304d4b7f1af71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.703ex; height:2.843ex;" alt="{\displaystyle S(n)}" loading="lazy"> is always at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">. A number <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> greater than 4 is a <a href="Prime_number" title="Prime number">prime number</a> if and only if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S(n)=n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S(n)=n}</annotation>

</semantics>

</math><img src="./5b35177bc49e2b1c9466b2fb0c6a0da6a8e5ce9a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.196ex; height:2.843ex;" alt="{\displaystyle S(n)=n}" loading="lazy">.<a href="#cite_note-6">[6]</a> That is, the numbers <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> for which <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S(n)}</annotation>

</semantics>

</math><img src="./896aa95cb194816f48a89fecd7e304d4b7f1af71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.703ex; height:2.843ex;" alt="{\displaystyle S(n)}" loading="lazy"> is as large as possible relative to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> are the primes. In the other direction, the numbers for which <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S(n)}</annotation>

</semantics>

</math><img src="./896aa95cb194816f48a89fecd7e304d4b7f1af71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.703ex; height:2.843ex;" alt="{\displaystyle S(n)}" loading="lazy"> is as small as possible are the factorials: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S(k!)=k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S(k!)=k}</annotation>

</semantics>

</math><img src="./c8ef7215346202c97e93a3ecdaf8014c85b87ead.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.476ex; height:2.843ex;" alt="{\displaystyle S(k!)=k}" loading="lazy">, for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\geq 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\geq 1}</annotation>

</semantics>

</math><img src="./d30d7dcf305b7bce39d36df72fe3985b47aa9961.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.472ex; height:2.343ex;" alt="{\displaystyle k\geq 1}" loading="lazy">.

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S(n)}</annotation>

</semantics>

</math><img src="./896aa95cb194816f48a89fecd7e304d4b7f1af71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.703ex; height:2.843ex;" alt="{\displaystyle S(n)}" loading="lazy"> is the smallest possible <a href="Degree_of_a_polynomial" title="Degree of a polynomial">degree</a> of a <a href="Monic_polynomial" title="Monic polynomial">monic polynomial</a> with integer coefficients, whose values over the integers are all divisible by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">.<a href="#cite_note-oeis-1">[1]</a>

For instance, the fact that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S(6)=3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S(6)=3}</annotation>

</semantics>

</math><img src="./046e44f91cb2a7c1e60b43195acab3606673de0a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.732ex; height:2.843ex;" alt="{\displaystyle S(6)=3}" loading="lazy"> means that there is a <a href="Cubic_polynomial" class="mw-redirect" title="Cubic polynomial">cubic polynomial</a> whose values are all zero <a href="Modular_arithmetic" title="Modular arithmetic">modulo</a> 6, for instance the polynomial

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(x-1)(x-2)=x^{3}-3x^{2}+2x,}</annotation>

</semantics>

</math>

but that all quadratic or linear polynomials (with leading coefficient one) are nonzero modulo 6 at some integers.

In one of the advanced problems in <a href="The_American_Mathematical_Monthly" title="The American Mathematical Monthly">The American Mathematical Monthly</a>, set in 1991 and solved in 1994, <a href="Paul_Erd%C5%91s" title="Paul Erdős">Paul Erdős</a> pointed out that the function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S(n)}</annotation>

</semantics>

</math><img src="./896aa95cb194816f48a89fecd7e304d4b7f1af71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.703ex; height:2.843ex;" alt="{\displaystyle S(n)}" loading="lazy"> coincides with the largest <a href="Prime_factor" class="mw-redirect" title="Prime factor">prime factor</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> for "almost all" <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> (in the sense that the <a href="Asymptotic_density" class="mw-redirect" title="Asymptotic density">asymptotic density</a> of the set of exceptions is zero).<a href="#cite_note-7">[7]</a>

<div class="mw-heading mw-heading2"><h2 id="Computational_complexity">Computational complexity</h2></div>

The Kempner function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S(n)}</annotation>

</semantics>

</math><img src="./896aa95cb194816f48a89fecd7e304d4b7f1af71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.703ex; height:2.843ex;" alt="{\displaystyle S(n)}" loading="lazy"> of an arbitrary number <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> is the maximum, over the <a href="Prime_power" title="Prime power">prime powers</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p^{e}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p^{e}}</annotation>

</semantics>

</math><img src="./03d8780732f14fd53dea93193e8d041521170697.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.257ex; height:2.676ex;" alt="{\displaystyle p^{e}}" loading="lazy"> dividing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S(p^{e})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S(p^{e})}</annotation>

</semantics>

</math><img src="./ecc8408c1f2265bbb141aeddcd9c9676691b4ab9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.476ex; height:2.843ex;" alt="{\displaystyle S(p^{e})}" loading="lazy">.<a href="#cite_note-history3-4">[4]</a>

When <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> is itself a prime power <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p^{e}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p^{e}}</annotation>

</semantics>

</math><img src="./03d8780732f14fd53dea93193e8d041521170697.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.257ex; height:2.676ex;" alt="{\displaystyle p^{e}}" loading="lazy">, its Kempner function may be found in <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a> by sequentially scanning the multiples of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> until finding the first one whose factorial contains enough multiples of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy">. The same <a href="Algorithm" title="Algorithm">algorithm</a> can be extended to any <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> whose prime factorization is already known, by applying it separately to each prime power in the factorization and choosing the one that leads to the largest value.

For a number of the form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=px}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=px}</annotation>

</semantics>

</math><img src="./6a766339ca8af47389766116e119a838c7bea721.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.992ex; height:2.009ex;" alt="{\displaystyle n=px}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> is prime and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> is less than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy">, the Kempner function of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy">.<a href="#cite_note-history3-4">[4]</a> It follows from this that computing the Kempner function of a <a href="Semiprime" title="Semiprime">semiprime</a> (a product of two primes) is computationally equivalent to finding its <a href="Prime_factorization" class="mw-redirect" title="Prime factorization">prime factorization</a>, believed to be a difficult problem. More generally, whenever <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> is a <a href="Composite_number" title="Composite number">composite number</a>, the <a href="Greatest_common_divisor" title="Greatest common divisor">greatest common divisor</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S(n)}</annotation>

</semantics>

</math><img src="./896aa95cb194816f48a89fecd7e304d4b7f1af71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.703ex; height:2.843ex;" alt="{\displaystyle S(n)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> will necessarily be a nontrivial <a href="Divisor" title="Divisor">divisor</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, allowing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> to be factored by repeated evaluations of the Kempner function. Therefore, computing the Kempner function can in general be no easier than factoring composite numbers.

<div class="mw-heading mw-heading2"><h2 id="References_and_notes">References and notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-oeis-1">^ <a href="#cite_ref-oeis_1-0">a</a> <a href="#cite_ref-oeis_1-1">b</a> Called the Kempner numbers in the <a href="Online_Encyclopedia_of_Integer_Sequences" class="mw-redirect" title="Online Encyclopedia of Integer Sequences">Online Encyclopedia of Integer Sequences</a>: see <style data-mw-deduplicate="TemplateStyles:r1238218222">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFSloane_"A002034"" class="citation web cs1"><a href="Neil_Sloane" title="Neil Sloane">Sloane, N. J. A.</a> (ed.). <a rel="nofollow" class="external text" href="https://oeis.org/A002034">"Sequence A002034 (Kempner numbers: smallest number m such that n divides m!)"</a>. The <a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">On-Line Encyclopedia of Integer Sequences</a>. OEIS Foundation.</cite>

</li>

<cite id="CITEREFLucas1883" class="citation journal cs1"><a href="Fran%C3%A7ois_%C3%89douard_Anatole_Lucas" class="mw-redirect" title="François Édouard Anatole Lucas">Lucas, E.</a> (1883). "Question Nr. 288". <a href="Mathesis_(journal)" title="Mathesis (journal)">Mathesis</a>. 3: 232.</cite>

</li>

<cite id="CITEREFNeuberg1887" class="citation journal cs1"><a href="Joseph_Jean_Baptiste_Neuberg" title="Joseph Jean Baptiste Neuberg">Neuberg, J.</a> (1887). "Solutions de questions proposées, Question Nr. 288". <a href="Mathesis_(journal)" title="Mathesis (journal)">Mathesis</a>. 7: 68–69.</cite>

</li>

<cite id="CITEREFKempner1918" class="citation journal cs1">Kempner, A. J. (1918). "Miscellanea". <a href="The_American_Mathematical_Monthly" title="The American Mathematical Monthly">The American Mathematical Monthly</a>. 25 (5): 201–210. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2972639">10.2307/2972639</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2972639">2972639</a>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFHungerbühlerSpecker2006" class="citation journal cs1">Hungerbühler, Norbert; <a href="Ernst_Specker" title="Ernst Specker">Specker, Ernst</a> (2006). <a rel="nofollow" class="external text" href="http://www.emis.de/journals/INTEGERS/papers/g23/g23.Abstract.html">"A generalization of the Smarandache function to several variables"</a>. Integers. 6: A23, 11. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2264838">2264838</a>.</cite>

</li>

<cite id="CITEREFR._Muller1990" class="citation journal cs1">R. Muller (1990). <a rel="nofollow" class="external text" href="http://www.gallup.unm.edu/~smarandache/SFJ1.pdf">"Editorial"</a> (PDF). Smarandache Function Journal. 1: 1. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>84-252-1918-3</bdi>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFErdősKastanas1994" class="citation journal cs1"><a href="Paul_Erd%C5%91s" title="Paul Erdős">Erdős, Paul</a>; Kastanas, Ilias (1994). <a rel="nofollow" class="external text" href="http://www-fourier.ujf-grenoble.fr/~marin/une_autre_crypto/articles_et_extraits_livres/irationalite/Erdos_P._Kastanas_I.The_smallest_factorial...-.pdf">"The smallest factorial that is a multiple of n (solution to problem 6674)"</a> (PDF). <a href="The_American_Mathematical_Monthly" title="The American Mathematical Monthly">The American Mathematical Monthly</a>. 101: 179. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2324376">10.2307/2324376</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2324376">2324376</a>.</cite>.

</li>

</ol></div></div>

This article incorporates material from <a rel="nofollow" class="external text" href="https://planetmath.org/SmarandacheFunction">Smarandache function</a> on <a href="PlanetMath" title="PlanetMath">PlanetMath</a>, which is licensed under the Creative Commons Attribution/Share-Alike License.

</div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-06-25" href="https://en.wikipedia.org/wiki/?title=Kempner_function&oldid=1231011926">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>